package main

import "fmt"

/**
给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0开头。



示例 1：


输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]


提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
*/

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	return next(l1, l2, 0)
}

func next(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
	amount := l1.Val + l2.Val + carry
	amount, carry = amount%10, amount/10
	var nextNode *ListNode = nil
	if l1.Next != nil || l2.Next != nil || carry > 0 {
		if l1.Next == nil {
			l1.Next = &ListNode{}
		}
		if l2.Next == nil {
			l2.Next = &ListNode{}
		}
		nextNode = next(l1.Next, l2.Next, carry)
	}
	return &ListNode{Val: amount, Next: nextNode}
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func put(arr []int) *ListNode {
	node := &ListNode{}
	node.putVal(arr)
	return node
}

func (t *ListNode) putVal(arr []int) {
	t.Val = arr[0]
	if len(arr) > 1 {
		nextNode := &ListNode{}
		t.Next = nextNode
		nextNode.putVal(arr[1:])
	}
}

func (t *ListNode) print() {
	if t.Next != nil {
		t.Next.print()
	}
	fmt.Println(t.Val)
}

func main() {
	l1 := put([]int{2, 4, 3})
	l2 := put([]int{5, 6, 4})
	numbers := addTwoNumbers(l1, l2)
	numbers.print()
}
